package com.cuz.daileetcode.bat100;

/***
 * https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/
 */
public class 相邻K数合并代价 {
    public static void main(String[] args) {
        int[] ints = {3,2,4,1};
        //(n-1)%(k-1)==0
        System.out.println(mergeStones1(ints, 2));
        System.out.println(mergeStones2(ints, 2));
    }

    public static int mergeStones1(int[] stones, int k) {
        int[] preSum = preSum(stones);
        return process(k, 1, 0, stones.length - 1, preSum);
    }

    private static int[] preSum(int[] arr) {
        int[] preSum = new int[arr.length];
        preSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            preSum[i] = preSum[i - 1] + arr[i];
        }
        return preSum;
    }

    private static int process(int k, int part, int l, int r, int[] preSum) {
        if (l == r) {
            return part == 1 ? 0 : -1;
        }
        if (part == 1) {
            int ans = process(k, k, l, r, preSum);
            if (ans == -1) {
                return -1;
            }
            //stones=[4 1 2 3]
            //preSum=[4,5,7,10]
            //l=1 r=3  ==>合并 1 2 3
            return ans + preSum[r] - ((l > 0) ? preSum[l] : 0);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = l; i < r; i += k - 1) {
            //l~i 1份  i+1~r p-1份
            int leftPart = process(k, 1, l, i, preSum);
            if (leftPart == -1) {
                continue;
            }
            int rightPart = process(k, part - 1, i + 1, r, preSum);
            if (rightPart == -1) {
                continue;
            }
            ans = Math.min(ans,leftPart+rightPart);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
//1 (2 3)( 4 1)
    //1 3 6 10 11
    //

    public static int mergeStones2(int[] stones, int k) {
        int[] preSum = preSum(stones);
        int[][][] dp = new int[stones.length][stones.length][k + 1];
        return process2(k, 1, 0, stones.length - 1, preSum,dp);
    }
    private static int process2(int k, int part, int l, int r, int[] preSum, int[][][] dp) {
        if (dp[l][r][part] != 0) {
            return dp[l][r][part];
        }
        int res = -1;
        if (l == r) {
            res = (part == 1 ? 0 : -1);
            dp[l][r][part] = res;
            return res;
        }
        if (part == 1) {
            int ans = process2(k, k, l, r, preSum,dp);
            if (ans == -1) {
                res = -1;
            } else {
                //stones=[4 1 2 3]
                //preSum=[4,5,7,10]
                //l=1 r=3  ==>合并 1 2 3
                res = ans + preSum[r] - ((l > 0) ? preSum[l] : 0);
            }
        } else {
            int ans = Integer.MAX_VALUE;
            for (int i = l; i < r; i += k - 1) {
                //l~i 1份  i+1~r p-1份
                int leftPart = process2(k, 1, l, i, preSum,dp);
                if (leftPart == -1) {
                    continue;
                }
                int rightPart = process2(k, part - 1, i + 1, r, preSum,dp);
                if (rightPart == -1) {
                    continue;
                }
                ans = Math.min(ans, rightPart+leftPart);
            }
            res = ans;
        }
        dp[l][r][part] = res;
        return res;
    }


}
